import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import org.junit.Test;

public class MyTest {
    /* public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> ans=new ArrayList<Integer>();
        int[] color=new int[graph.length];
        for(int i=0;i<graph.length;i++){
            if(DFS(i, graph, color)){
                ans.add(i);
            }
        }
        return ans;
    }
    private boolean DFS(int start,int[][] graph,int[] color){
        if(color[start]==1){
            return true;
        }
        if(color[start]==2){
            return false;
        }
        color[start]=2;
        for(int next:graph[start]){
            if(!DFS(next, graph, color)){
                return false;
            }
        }
        color[start]=1;
        return true;
    } */
    
    /* public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if(newColor!=image[sr][sc]){
            DFS(image, sr, sc, newColor, image[sr][sc]);
        }
        return image;
    }
    private void DFS(int[][] image, int sr, int sc, int newColor,int color){
        image[sr][sc]=newColor;
        if(sr-1>=0&&image[sr-1][sc]==color){
            DFS(image, sr-1, sc, newColor, color);
        }
        if(sc-1>=0&&image[sr][sc-1]==color){
            DFS(image, sr, sc-1, newColor, color);
        }
        if(sr+1<image.length&&image[sr+1][sc]==color){
            DFS(image, sr+1, sc, newColor, color);
        }
        if(sc+1<image[0].length&&image[sr][sc+1]==color){
            DFS(image, sr, sc+1, newColor, color);
        }
    } */
    int maxArea=0;
    int area=0;
    public int maxAreaOfIsland(int[][] grid) {
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                area=0;
                DFS(grid, i, j );
            }
        }
        return maxArea;
    }
    private void DFS(int[][] grid,int i,int j){
        if(grid[i][j]!=1){
            return;
        }
        area++;
        grid[i][j]=2;
        if(i-1>=0){
            DFS(grid, i-1, j);
        }
        if(j-1>=0){
            DFS(grid, i, j-1);
        }
        if(i+1<grid.length){
            DFS(grid, i+1, j);
        }
        if(j+1<grid[0].length){
            DFS(grid, i, j+1);
        }
        maxArea=Math.max(maxArea,area);
    }
    
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
        

    public ListNode detectCycle(ListNode head) {
        ListNode slow=head,fast=head;
        do{
            slow=slow.next;
            fast=fast.next.next;
        }while(slow!=fast);
        while(head!=slow){
            head=head.next;
            slow=slow.next;
        }
        return head;
    }

    public int[] dailyTemperatures(int[] temperatures) {
        int[] ans=new int[temperatures.length];
        Stack<Integer> stack=new Stack<Integer>();
        for(int i=0;i<temperatures.length;i++){
            while(!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[i]){
                ans[stack.peek()]=i-stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return ans;
    }
    
    public int findDuplicate(int[] nums) {
        int slow=0,fast=0;
        do{
            slow=nums[slow];
            fast=nums[nums[fast]];
        }while(nums[slow]!=nums[fast]);
        int p=0;
        while(p!=slow){
            p=nums[p];
            slow=nums[slow];
        }
        return p;
    }

    public int countSubstrings(String s) {
        boolean[][] dp=new boolean[s.length()][s.length()];
        int count=0;
        for(int i=0;i<s.length();i++){
            dp[i][i]=true;
            count++;
            if(i+1<s.length()&&s.charAt(i)==s.charAt(i+1)){
                dp[i][i+1]=true;
                count++;
            }
        }
        for(int i=s.length()-3;i>=0;i--){
            for(int j=s.length()-1;j>i;j--){
                if(dp[i+1][j-1]==true&&s.charAt(i)==s.charAt(j)){
                    dp[i][j]=true;
                    count++;
                }
            }
        }
        return count;
    }


    @Test
    public void test(){
        int[] nums={1,1,1};
        System.out.println(subarraySum(nums, 2));
    }
}
